1. Field of the Invention
The present invention relates to a Viterbi decoder for decoding the receive signal series encoded with an error correcting code by the operation of a processor in the method for decoding the error correcting code.
2. Description of the Prior Art
In the fields of communication and information processing, the reliability of communication and information processing, as the case may be, is required to be improved. For this purpose, a technique using xe2x80x9cerror correcting codexe2x80x9d has been proposed to assure correct receipt at the receiving end of the signals transmitted from the transmitting end. In recent years, a high-performance decoding method for the error correcting code has been required. One of the most effective method of decoding the error correcting code is the Viterbi decoding method which is a maximum likelihood decoding method for the receive signal series containing the error correcting code. This method has an especially superior ability of error correction, and therefore has been widely used.
An example of the Viterbi decoding method will be described. FIG. 22 is a diagram showing an example of the trellis used in the Viterbi decoding method. In the Viterbi decoding method, the maximum likelihood decoding is executed using the trellis shown in FIG. 22.
In FIG. 22, two branches entering each status Sk (k=0, 1, 2, . . . ) each have a value called a branch output. Also, the numerical value described under each status Sk is called a path metric which is the minimum sum of the branch metrics leading to the status Sk.
Assume, for example, that the current time is T1. First, in the status S0, the branch metric (humming distance) between each of the two branches (branch 0 and branch 1) entering the status S0 on the one hand and the receive signal series on the other is calculated.
Once the branch metrics (branch 0=1, branch 1=1) of branches 0, 1 are determined, the path metric of the status S0 with the branch 0 connected to the time point T0 one unit time before is used (which is conventionally preserved in a memory equipment), and added to the branch metric of the branch 0 as a value P1. Specifically, P1=branch metric of branch 0 (=1)+path metric of status S0 (=2)=3 is determined. In similar fashion, the sum P2 of the path metric of the status S2 with the branch 1 connected to T0 one unit time before and the branch metric of the branch 1 is determined. Specifically, P2=branch metric of branch 0 (=1)+path metric of status S2 (=101)=102 is determined.
Then, 21 and P2 are compared with each other, the smaller one of them (P1=3) is stored as a path metric for the status S0 at time point T1. Also, in FIG. 22, the selected branch 0 transfers from the status S0 one time unit before, and therefore the information bit xe2x80x9c0xe2x80x9d is input and stored. In the trellis shown in FIG. 22, thick solid lines indicate the path selected by the technique mentioned above.
After the forgoing processing has been executed for all the status Sk (k=0, 1, 2, . . . ) and all the time points, assume that the trellis is known to end at the status S3 at time point T2 by the negotiation beforehand between the transmitting and receiving ends. The thick surviving path of the trellis traced (called the back trace) toward time point T0 from the status S3 at the final time point T2. The decoded signal series can be output in the direction reverse to the input, if the bit xe2x80x9c0xe2x80x9d is output for a thick solid line and xe2x80x9c1xe2x80x9d for a thick dashed line.
As described above, in the Viterbi decoding method, the code series considered most likely to have been transmitted from the transmitting end is estimated thereby to eliminate the error in the transmission path.
The Viterbi decoder for realizing the Viterbi decoding method described above has already been proposed. The recent trend is toward the Viterbi decoder being configured not simply with hardware but with software (firmware) and a processor. In the case where the Viterbi decoder is realized using software, the processing speed is unavoidably reduced than in hardware, and therefore the amount of operation (processing amount) is required to be reduced. Especially, the maximum likelihood decoding method such as the Viterbi decoding method involves a comparatively large amount of operation, which must be reduced as far as possible.
Fujitsu Ltd. has proposed a Viterbi decoder for realizing the Viterbi decoding scheme with the operation using the processor (Japanese Patent Application Laid-Open No. 7-30438, hereinafter referred to as the prior art). In the prior art, in order to calculate the branch metric, branch metrics corresponding to the receive signal series are held as a table, and upon receipt of the receive signal series, an address is calculated from the receive signal series for accessing the table of the branch metrics. Then the branch metric corresponding to the address is read from the table, thereby reducing the operation amount required for calculating the branch metric.
In the prior art which is configured to read the branch metric from the table by random access, however, the operation for generating an address is required each time the branch metric is read, thereby posing the problem of the long time required for calculation of the branch metric.
Also, the branch metrics held in the table beforehand is so vast in amount that the storage capacity of the memory for storing the table is unavoidably increased.
The object of the present invention is to provide a Viterbi decoder in which the time required for calculating the branch metric can be shortened and the memory capacity required for the table used to calculate the branch metric can be reduced.
According to a first aspect of the invention, there is provided a Viterbi decoder for decoding the receive signal series encoded with an error correcting code, comprising a storage unit for storing a plurality of branch metrics, and a control unit for selecting a surviving path for each status using the branch metrics stored in the storage unit upon receipt of the receive signal series, wherein the storage unit is prepared in beforehand accordance with the pattern of the receive signal series and stores a plurality of tables holding the branch metrics corresponding to each status. Each table holds the branch metrics in such a manner that the branch metrics of the two branches entering each status are read by the control unit in the order of the branches constituting the trellis.
According to a second aspect of the invention, there is provided a Viterbi decoder for decoding the receive signal series encoded by an error correcting code, comprising a storage unit for storing a plurality of branch metrics, and a control unit for selecting a surviving path for each status using the branch metrics stored in the storage unit upon receipt of the receive signal series, wherein the storage unit is prepared beforehand in accordance with the pattern of the receive signal series and stores a plurality of tables holding the branch metrics corresponding to each status. In the case where the branch metric of one of the two branches entering a given status can be calculated by the branch metric of the other branch, each table holds only one of the branch metrics. In the case where the branch metric of only one of the two branches entering a given status is read from the table corresponding to the receive signal series, the control unit determines the other branch metric from the particular one branch metric.
For example, assuming that the output values of the two branches entering a given status are codes with bits of inverted signs, each table holds the branch metric of only one of the branches.
According to a third aspect of the invention, there is provided a Viterbi decoder for decoding the receive signal series encoded by an error correcting code, comprising a storage unit for storing a plurality of branch metrics, and a control unit for selecting a surviving path for each status by calculating the path metrics corresponding to the two branches entering each status using the branch metrics stored in the storage unit upon receipt of the receive signal series, wherein the storage unit is prepared in beforehand accordance with the pattern of the receive signal series and stores a plurality of tables holding the branch metrics corresponding to each status. Each table holds only one of the branch metrics of the two branches entering each status converted to be symmetric about zero (opposite signs of positive and negative), as a branch metric corresponding to the particular status. In the case where only one of the branch metrics of the two branches symmetric about zero is read from the table corresponding to the receive signal series, the control unit calculates the path metric corresponding to the two branches entering each status using the particular one branch metric.
According to a fourth aspect of the invention, there is provided a Viterbi decoder for decoding the receive signal series encoded by an error correcting code, comprising a storage unit for storing a plurality of branch metrics, and a control unit for selecting a surviving path for each status by calculating the path metrics corresponding to the two branches entering each status using the branch metrics stored in the storage unit upon receipt of the receive signal series, wherein the storage unit is prepared in beforehand accordance with the pattern of the receive signal series and stores a plurality of tables holding the branch metrics corresponding to each status. As a branch metric corresponding to each status, each table holds only one of the branch metrics of the two branches entering a given status from which the branch metric of the other branch can be determined, and further holds adjoining status having the same branch metric in a group. The control unit reads the grouped branch metrics from the table corresponding to the receive signal series, and calculates the path metric for each status corresponding to the branch metric thus read.
According to a fifth aspect of the invention, there is provided a Viterbi decoder for decoding the receive signal series encoded by an error correcting code, comprising a storage unit for storing a plurality of branch metrics, and a control unit for selecting a surviving path for each status by calculating the path metrics corresponding to the two branches entering each status using the branch metrics stored in the storage unit upon receipt of the receive signal series, wherein the storage unit is prepared in beforehand accordance with the pattern of the receive signal series and stores a plurality of tables holding the branch metrics corresponding to each status. As a branch metric corresponding to each status, each table holds only one of the branch metrics of the two branches entering a given status from which the branch metric of the other branch can be determined, and further holds adjoining status having the branch metrics of opposite signs of positive and negative in a group. The control unit reads the grouped branch metrics from the table corresponding to the receive signal series, and calculates the path metric for each status corresponding to the branch metric thus read.
According to a sixth aspect of the invention, there is provided a Viterbi decoder for decoding the receive signal series encoded by an error correcting code, comprising a storage unit for storing a plurality of branch metrics, and a control unit for selecting a surviving path for each status by calculating the path metrics corresponding to the two branches entering each status using the branch metrics stored in the storage unit upon receipt of the receive signal series, wherein the storage unit is prepared in beforehand accordance with the pattern of the receive signal series and stores a plurality of tables holding the branch metrics corresponding to each status. As a branch metric corresponding to each status, each table holds only one of the branch metrics of the two branches entering a given status from which the branch metric of the other branch can be determined, and further holds branches not having adjoining status but having the same branch metrics in a group in the case where adjoining status neither have the same branch metric nor have branch metrics of opposite signs of positive and negative. The control unit reads the grouped branch metrics from the table corresponding to the receive signal series, and calculates the path metric for each status corresponding to the branch metric thus read.
According to a seventh aspect of the invention, there is provided a Viterbi decoder for decoding the receive signal series encoded by an error correcting code, comprising a storage unit for storing a plurality of branch metrics, and a control unit for selecting a surviving path for each status using the branch metrics stored in the storage unit upon receipt of the receive signal series, wherein the storage unit stores a table shared by a specific receive signal series and a receive signal series having a pattern inverted-from that of the specific receive signal series, and wherein the control unit, upon receipt of the specific receive signal series or the receive signal series inverted from the first receive signal series, reads the branch metrics stored in the table and selects a surviving path for each status.
According to an eighth aspect of the invention, there is provided a Viterbi decoder for decoding the receive signal series encoded by an error correcting code, comprising a storage unit for storing a plurality of branch metrics, and a control unit for selecting a surviving path for each status by calculating the path metric corresponding to the two branches entering each status using the branch metrics stored in the storage unit upon receipt of the receive signal series, wherein in the case where the trellis determined by the negotiation with the transmitting end of the receive signal series and applied to the decoding of the receive signal series is such that the branch metric for each status corresponding to the receive signal series input to the control unit cannot be read by sequential access from the storage unit, the control unit converts the structure of the trellis into a state in which the branch metric can be read by sequential access, and produces a table holding the branch metric for each status corresponding to the trellis having the converted structure.
A Viterbi decoder according to this invention has a structure in which the branch metric table is accessible sequentially. As a result, the time required for reading the branch metrics from the branch metric table is shortened and so is the time required for calculating the path metrics.
Also, in a Viterbi decoder according to the invention, the branch metric table holds a plurality of branch metrics in a group. As a result, the number of times the branch metric table is accessed is reduced. Thus, both the amount of operation of the path metrics and the storage capacity of the branch metric memory can be reduced.
Also, in a Viterbi decoder according to the invention, the values of the branch metrics of the branches entering a given status are symmetric about zero. As a result, the amount of operation of the path metrics requiring repetitive calculations is reduced and so is the storage capacity of the branch metric memory.
As described above, with a Viterbi decoder according to this invention, the amount of operation for selecting a surviving path can be reduced. As a result, the time required for decoding the receive signal series can be shortened and so is the storage capacity of the branch metric memory.